Privacy issues have been limiting the successful commercialization of radio frequency identification (RFID) systems. The ability to trace RFID tags, and ultimately the individuals carrying them, is a major obstacle for the deployment of RFID systems in real life applications. Privacy activists have been concerned about the invasion of users' privacy by RFID tags, calling for the delay or even the abandonment of their deployment. In some cases, companies have been forced to repudiate their plans for RFID deployment in response to the threat of being boycotted over such privacy concerns. As a consequence of these threats, significant effort has been made in the direction of designing RFID systems that preserve the privacy of users.
The three main goals of RFID systems are identification, security, and privacy. Individually, these goals can be achieved relatively easily. However, achieving all the three goals simultaneously is a very challenging task for protocol designers. Identification, by itself, can be as easy as transmitting identifiers of tags in clear text. When combined with the privacy requirement, however, transmitting identifiers in clear text is obviously unacceptable. Adding security to the equation makes things even more complicated. To secure communicated messages against various types of attacks, the cryptographic parameters that are used must be sufficiently long. (The U.S. National Institute for Standards and Technology, NIST, has indicated that 80-bit encryption keys will no longer be secure for symmetric key cryptography by the year 2010.) If the length of the RFID tag identifiers that is used is sufficiently long, so that easily implemented attacks such as random guessing and exhaustive search have only a small probability of success, then searching a database to find those identifiers will be more time consuming and inefficient.
Earlier RFID protocols traded off identification efficiency in order to address all three goals of an RFID system. That is, the three goals were achieved, but the reader was required to perform a linear search among all the RFID tags in the system in order to identify the RFID tag currently being interrogated. In a typical protocol of this class, the reader interrogates the RFID tag by sending a random nonce, r1. The RFID tag generates another nonce, r2, computes h(ID, r1, r2), which is the hash of its identifier concatenated with r1 and r2, and then responds with r2 and the resulting hash value. Different protocols implement variants of this approach, but achieving this result is the main functional goal of this class of protocols. Upon receiving the RFID tag's response, the reader performs a linear search of all the RFID tags in the system, computing the hash of their identifiers with the transmitted nonce, until it finds a match. Obviously, unauthorized observers cannot correlate different responses of the same tag, as long as the nonce is never repeated.
Although this class of protocols can provide private identification, they lack the important scalability property. More specifically, this class of protocols may be suitable for small RFID systems, but becomes impractical as the number of tags in the system increases. In an RFID system with millions or billions of tags, performing a linear search for every identification run can be extremely cumbersome and time consuming. Thus, for a RFID system to be practical, it is desirable to employ an identification process that can break the barrier of linear search complexity.
An important step towards solving the scalability issue in RFID systems has been proposed in the prior art. This approach uses a tree structure, where each edge in the tree corresponds to a unique secret key, each leaf of the tree corresponds to a unique tag in the system, and each tag carries the set of keys on the corresponding path from the root of the tree to its leaf. The RFID tag is identified and authorized, by its knowledge of the secret keys along its corresponding path.
However, managing tags in a tree structure based on the secret keys that they possess poses a serious security threat to a RFID system. Every compromised tag will reveal the secret keys from the root of the tree to its leaf. Since these keys are shared by many tags in the system, compromising one tag will reveal secret information about all tags sharing a subset of these keys.
Existing privacy preserving RFID identification schemes, other than tree-based schemes, have a search time complexity of O(NT), where NT is the number of tags in the system. A clear advantage of the tree-based scheme is that the search time complexity is reduced to O(log NT), which represents a big step towards scalable RFID systems.
Many protocols for low-cost RFID systems have been proposed over the past few years. Some have been shown to be secure, but many have been broken or fail to achieve the claimed properties. For example, one prior approach proposed a privacy preserving identification protocol. In this protocol, when an RFID reader is used to identify a tag within its communication range, it sends a request. The RFID tag generates a random number r, hashes it with its secret ID, and responds with s=(h(ID,r),r), where ID is unique for each tag in the system. Upon receiving the RFID tag's response, the reader performs a linear search, hashing the received r with all the ID's in the database until a match is found. Obviously, an adversary interrogating the same tag multiple times will receive different responses each time, and thus, will be unable to invade the privacy of the RFID tag.
Another prior art protocol differs from the preceding one, because it applies hashing on a non-static identifier instead of a randomized response. Two hash functions, h1 and h2, are used in the implementation of this protocol. Each tag is initialized with a unique ID, and every time that the RFID tag is interrogated, it responds with h1 (ID), which is the hash of its ID. Following every response, the RFID tag replaces its ID by h2 (ID). To identify a tag, the database constructs NT hash chains (one for each tag), until it finds a match. This protocol also provides private identification.
Another lightweight prior art protocol provides that each tag, Ti, has a secret, which is denoted ti, that is known to the database. The reader interrogates the RFID tag by sending a random nonce r1. The RFID tag generates another random number r2, evaluates M1=tir2 and M2=hti(r1,r2), where hti is a keyed hash function, and sends M1 and M2 to the reader. Upon receiving the RFID tag's response, the reader searches the database for the ti that satisfies M2=hti(r1,M1,ti). Having identified the RFID tag, the reader responds with a message that allows the RFID tag to authenticate the reader and update its secret ti.
All of these protocols require searching all of the RFID tags in the database until a match is found in order to identify a single tag. Therefore, it can be said that they belong to the linear-time identification class of protocols, which inherently require more time as the number of tags in a database increases.
The second class of protocols is the logarithmic-time identification class, where tag identification requires searching for a time that is proportional to the logarithm of the number of tags in the system.
In the first logarithmic-time identification protocol that appeared in the prior art, to avoid the need to search the entire database for every identification, the RFID tags were arranged in a tree structure based on a secret key possessed by authorized users. The tree is then built such that each edge has a unique secret key. Tags are stored at the leaves of the tree, and each tag stores the keys in the path from the root to its leaf By traversing the tree from top to bottom, the reader can identify tags by the secret key possessed by an authorized user.
Although reducing search-time complexity can be considered a milestone in the design of scalable RFID protocols, it introduces a new security threat. Arranging tags in a tree, based on their secret keys, implies that different tags will share secret information depending on their position in the tree. Therefore, compromising a subset of tags in the system can dangerously undermine the security of other uncompromised tags. In fact, in at least one of the prior art approaches, it has been shown that, by compromising only 20 tags in a system containing 220 tags, an adversary can trace an uncompromised tag with a probability close to one.
The advantage of reducing the search-time complexity was attractive but it is not possible to overlook the protocol as a result of the new threat it introduced. In an attempt to mitigate the problem of tag compromise attack, others have proposed a dynamic key update authentication protocol that is similar to the tree-based protocol, but adds the step of updating the tree after every successful protocol run. The idea of key update improves the security of the protocol, but does not provide security against a compromise attack. More precisely, in a system that contains 220 tags, an adversary compromising 20 tags will still have a 60% chance of tracing an uncompromised tag.
To address the problem of private identification in RFID systems, it would thus be desirable to employ a protocol that not only breaks the linear search complexity barrier, but also improves on the efficiency of the logarithmic search complexity and enables tag identification with constant-time search complexity. Unlike tree-based protocols, such a protocol should also be resilient to tag compromise attacks, so that compromising a subset of tags in the system, regardless of the size of the subset, should not affect the security of the remaining uncompromised tags.